# 给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

# 示例:

# 输入: "25525511135"
# 输出: ["255.255.11.135", "255.255.111.35"]

# 来源：力扣（LeetCode）
# 链接：https://leetcode-cn.com/problems/restore-ip-addresses
# 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
from typing import List


class Solution:
    def __init__(self):
        self.res = []

    def restoreIpAddresses(self, s: str) -> List[str]:
        if len(s) < 4 * 1 or len(s) > 4 * 3:
            return []
        self.recall(s, 0, "")
        return self.res

    def recall(self, s, index, l):
        if index == 4 and s == "":
            self.res.append(l)
            return

        for i in range(min(3, len(s))):
            print("s[:i+1]")
            if self.is_valid(s[:i+1]):
                if l:
                    tmp = l + "." + s[:i+1]
                else:
                    tmp = s[:i+1]
                self.recall(s[i+1:], index+1, tmp)

    def is_valid(self, num: str):
        if num == "":
            return False
        if len(num) > 3:
            return False
        if str(int(num)) != num:
            return False
        return 0 <= int(num) <= 255


print("res=", Solution().restoreIpAddresses("25525511135"))

def test():
    assert Solution().restoreIpAddresses("010010") == ["0.10.0.10","0.100.1.0"]
